package leetcode.array;

/*
1207. 独一无二的出现次数

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：
输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：
输入：arr = [1,2]
输出：false

示例 3：
输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true

提示：
1 <= arr.length <= 1000
-1000 <= arr[i] <= 1000
*/

import java.util.*;

public class UniqueOccurrences1207 {
    public static void main(String[] args) {
//        int[] arr = new int[]{1,2,2,1,1,3};
//        int[] arr = new int[]{1,2};
//        int[] arr = new int[]{26,2,16,16,5,5,26,2,5,20,20,5,2,20,2,2,20,2,16,20,16,17,16,2,16,20,26,16};
        int[] arr = new int[]{3,5,-2,-3,-6,-6};

        System.out.println(Arrays.toString(arr));
        long start1 = System.currentTimeMillis();
        System.out.println(test(arr));
        long end2 = System.currentTimeMillis();
        System.out.println("code run cost :"+(end2-start1)+" ms");
    }

    private static boolean test(int[] arr) {

//        return settle1(arr);
        return settle2(arr);
    }

    // 常规解法，两个hashmap搞定，其中一个hashmap也可以换成set
    private static boolean settle1(int[] arr) {
        if(null == arr || 0 == arr.length)
            return false;

        if(1 == arr.length)
            return true;
        if(2 == arr.length)
            if(arr[0] != arr[1])
                return false;
            else
                return true;

        Map arrCnt = new HashMap();
        Map cntMap = new HashMap();
        for(int i = 0; i < arr.length; i++) {
            if(!arrCnt.containsKey(arr[i]))
                arrCnt.put(arr[i], 1);
            else {
                int c = (int) arrCnt.get(arr[i]);
                arrCnt.put(arr[i], c + 1);
            }
        }

        Object[] keys = arrCnt.keySet().toArray();
        for(Object key : keys) {
            if(!cntMap.containsKey(arrCnt.get(key)))
                cntMap.put(arrCnt.get(key), arrCnt.get(key));
            else
                return false;
        }

        return true;
    }

    // 解法2，先排序，再计数，set容器助攻
    private static boolean settle2(int[] arr) {
        if(null == arr || 0 == arr.length)
            return false;

        if(1 == arr.length)
            return true;
        if(2 == arr.length)
            if(arr[0] != arr[1])
                return false;
            else
                return true;

        Arrays.sort(arr);
        Set s = new HashSet();
        int c = 1;
        for(int i = 1; i < arr.length; i++) {
            if(arr[i] != arr[i - 1]) {
                if (!s.add(c))
                    return false;

                c = 1;
            }
            else
                c++;
        }

        return true;
    }
}
